Pacwar

All material on this website is © Devika Subramanian, 2007-2017. Please request permission from devika@rice.edu for use of the material, and please acknowledge this site in your material.

The Pacwar Project

This problem is about designing killer species that live in an imaginary world called PAC-world, created by Donald Knuth of Stanford University. PAC-world is inhabited by several species of tiny creatures called PAC-mites, all of which are engaged in a constant struggle for survival with every other species. Each individual mite lives out its short lifetime by following a small set of deterministic rules and interacting only with its immediate surroundings. However, in large numbers, the PAC-mites of a species combine to form complex patterns of behavior, which enable them to compete with PAC-mites of other species. Your goal is to design a species that will annihilate every other species in this world in a one-on-one duel.

PAC-world and PAC-mites

• PAC-world consists of a grid of discrete cells, measuring 21 cells horizontally by 11 cells vertically. The world is completely surrounded by insurmountable barriers that occupy the outermost cells. Therefore, the actual world measures 19 cells by 9 cells. In the simulator, the barriers are not displayed, so only the 19x9 region is visible.

• Each cell may be occupied by a blob (i.e. an empty cell) or a PAC-mite. The PAC-mites are represented by pacman-like symbols. PAC-mites can be facing any of the cardinal directions (right and left, up and down). Direction 0 is used to indicate a right-facing mite, 1 to indicate an upward-facing mite, 2 to indicate a left-facing mite, and 3 to indicate a downward-facing mite.

• PAC-mites have a life span of 4 rounds. Their age (0,1,2,3) is represented by the number of rings at their centers, and they are colored according to the species to which they belong. The number of rings a PAC-mite has corresponds to the age of the mite and its power. A ringless mite has just been born, while a mite with three rings has been around for the past three rounds. Since a mite dies after four time rounds, no mite has more than three rings. In the world depicted above there are five red PAC-mites of age 1 and five newborn blue mites (age 0).

• Since age and the direction a PAC-mite faces are independent, there are sixteen possible configurations for a PAC-mite of any given species.

The Dynamics of PAC-world

• The contents of PAC-world change deterministically in discrete steps of time (rounds). This transition function is completely local — that is, the contents of a cell at time t+1 depend only upon the contents of that cell and its four neighboring cells at time t. In this transition, which is described below, each mite

  • ages,
  • possibly changes direction,
  • possibly causes a baby mite to be born in the cell that it was facing,
  • possibly dies,
  • or is replaced by a mite of the opposing species.

• The transition function is as follows:

  • A cell containing a blob (empty cell) at time t also contains a blob at time t+1, unless there is a birth into that cell (see U below).

  • A cell containing a k-ringed PAC-mite at time t will normally contain a k+1 ringed PAC-mite of the same species at time t+1. There are two exceptions to this rule:

    • If the PAC-mite already has 3 rings at time t, it dies of old age and will normally revert to a blob at time t+1.
    • If the cell which the PAC-mite inhabits is being attacked by hostile PAC-mites, the normal aging process may be overridden as explained below. If neither of the above conditions hold, the k+1-ringed mite will turn (see W, X, Y, and Z below).

  • If a cell containing a PAC-mite is being attacked by one or more PAC-mites of a different species at time t, then one of these rules applies.

    • If all of the most powerful attackers are friendly, the PAC-mite in the cell ages normally, as described above.
    • If there is a unique most powerful attacker which is of a different species, the mite is replaced by a baby enemy mite (see V below).
    • Otherwise, the cell is being attacked by at least two different equally powerful PAC-mites, at least one of which is hostile. In this case, the competition for the cell is so intense that the PAC-mite is destroyed, leaving only a blob behind.

• All PAC-mites of a given species have a common genetic code. The PAC-mite genetic code has 50 components, we will call genes. Each gene takes on one of four values: 0, 1, 2 or 3. Thus there are 4⁵⁰ possible species of PAC-mites. We need a small amount of notation to describe the function of the genes. A turn is a rotation of 90 degrees counter-clockwise. We use l to represent an age (0..3), e represents the difference between directions of mites A and B (in the number of turns it takes A to face B’s direction) (0..3), and k is an age (0..3). The genes and their general functions are:

  • [U] If an empty cell has exactly 1 oldest mite facing it, a new baby of that species is born there, U l turns from the direction its “mother” is facing, where l is the age of the mother.

  • [V] If a mite (she) is facing an enemy mite (he) and is the single, strongest mite facing him, he is replaced with a baby of her species, V el turns from the direction she is facing, where e is the difference between his and her directions, and her age is l.

  • [W] If a mite survives this round and is facing a barrier (i.e., is at the edge of PAC-world), it turns W k times, where k is the age of the mite.

  • [X] If a mite survives this round and is facing a blob, it turns X k times, where k is the age of the mite.

  • [Y] If a mite survives this round and is facing a friendly mite, it turns Y ek times, where e is the difference between the mite’s and his friend’s directions and k is this mite’s age.

  • [Z] If a mite survives this round and is facing an enemy mite, it turns Z ek times, where e is the difference between the mite’s and his enemy’s directions and k is this mite’s age.

Examples

Here are a few examples to aid in the understanding of the laws of PAC-world.

• Two PAC-mites A and B both face a certain cell, but A has more rings than B does. If the cell contains another mite of A’s species, this mite will age normally. If instead it contains a blob or mite of some other species, it will now contain a baby mite of A’s species. Simultaneously A and B change direction and age, or they are consumed by some other mite attacking them.

• Four PAC-mites, A, B, C and D all aim at a certain cell. A and B both have three rings, while C and D have two or fewer rings. If both A and B are of the same species, and the cell also contains a mite of this species, the mite will be allowed to age normally. Otherwise, the cell will contain a blob at the next time step.

• Two adjacent PAC-mites A and B of different species face each other. Assuming they are isolated from other attacking mites, they will cause baby mites b and a to occupy the previous sites of A and B respectively. These newborn mites might possibly be attacking each other as well.

How duels between species are evaluated

Duels are held only between pairs of species. Duels will continue until one species has been completely eliminated, or until 500 time units have passed. If neither species has won after 500 time units, the relative populations of the two species will be used to determine the score of the duel. Each duel is worth a total of 20 points. These 20 points will be divided between the two species as follows:

Observe that this scoring system gives significant advantage to species that actually destroy the opposing species rather than just outnumbering them. The reason for this complicated scoring system is that the set of all PAC-mite species is probably not a totally ordered set. Thus, it is possible that no clear winner would emerge from the competition if we simply considered the number of wins/losses/draws. The scoring system makes it unlikely that this will occur.

The task

Your mission is to find a PAC-mite species that will annihilate the PAC-mites submitted by your classmates in a round-robin duel. All the primary code resources for the project are here.

Getting started

Download the code. Unzip the folder and you will see a sub-folder named C. Open up a terminal window and navigate to that subfolder. Then start up the Pacwar simulator with “myWish -f PacWar.tcl”. The PacWar window shown at the top of this page will open up and you can play with mites of your own design. You can also use it to understand the rules of PacWar.

What to hand in

• A PAC-mite for the competition: Each team will submit their best entry into a round-robin duel on November 29, 2017, by noon as a private post on Piazza. We will set up projection equipment to watch duels on a big screen on November 29, 2017 in McMurtry Auditorium at 7 pm. Pizza will be served.

• The report: Prepare the final report containing information about your experiments to date, variations on search algorithms you tried, your current knowledge of the search space topology, and your final strategy for devising a killer gene. Instructions on how to write this report are here. The report is due on December 1, 2017. You have the option of turning in a near final draft to me by November 22, 2017 and I will give you feedback in two days. December 1, 2017 is the last day to submit your final report. It is due at 8 pm on Canvas.

• Interim progress reports (blogs) and draft of final report: Interim progress reports (with due dates indicated in the course schedule) are an important deliverable for this project. They should be 2-3 pages in length and they should provide a description of your results to date as well as your analysis and interpretation, clearly indicating the progress you have made since the previous report.
  Please use the blogs.rice.edu site for your blog and set it up so that I can read and comment on your post. You may or may not choose to share it with other groups in the class. I expect to see discussion of your overall strategy to find the killer gene, what hypotheses you had about the search space, how it influenced your design of the exploration algorithm, what heuristics you used to guide your search, what you thought were more profitable regions, how well they worked, how you revised your hypotheses, your algorithms, etc. These interim progress reports will be returned to you with comments. You are encouraged to use this feedback facility to help with writing your final report and also to get technical suggestions from me on how to best direct your search efforts. You have the option of turning in a near final draft of your report to me on November 22 and get feedback to help you with fine tuning your final report, which is due on December 1 at 8 pm on Canvas.